package com.leetcode.no322;

import java.util.*;

public class Solution {
    public int coinChange(int[] coins, int amount) {
        // 数组大小为 amount + 1，初始值也为 amount + 1
        int[] dp = new int[amount + 1];

        // 凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币）
        for (int i = 1; i <= dp.length - 1; i++) {
            dp[i] = amount + 1;
        }


        for (int i = 0; i <= dp.length - 1; i++) {
            for (int coin : coins) {
                // 一个硬币的值就超过了要凑的钱
                if (i < coin) {
                    continue;
                }
                if(i == coin){
                    dp[i] = 1;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }

}
